Geometric definition is an essential element in the design of practically any object to be manufactured. Until recently, geometric definition was performed primarily by drafting scale drawings of the object. In the last two decades, computer-aided geometric design (CAGD) has largely supplanted drafting. In CAGD, mathematical representations of an object's geometry are stored in computer memory and manipulated by the computer user. Sometimes the product of a CAGD design is scale drawings produced on a plotting device; in other cases a CAGD representation of the object is transmitted to numerical-control (NC) machinery for automated production of the object. The CAGD representation may also serve as a basis for analysis and evaluation of the design aside from visual aspects, e.g. finite-element stress analysis.
One well-known example of a CAGD program is AutoCAD (R), produced by AutoDesk, Inc. of Sausalito, Calif. Initially a two-dimensional environment simulating the drafting process on paper, AutoCAD now provides a three-dimensional environment in which many types of geometric entities including points, lines, curves, surfaces and solids can be defined, positioned, and edited to build up extremely precise definitions of highly complex objects. There are other CAGD programs which are much less general than AutoCAD, but are better adapted to specialized purposes; e.g. FAIRLINE (R) by AeroHydro, Inc., which is adapted to the special task of creating fair surfaces for ship hull design. CAGD programs for workstation and mainframe computers, for example IGDS (R) by Intergraph Corp., Huntsville, Ala., provide more flexible surface and solid modeling entities, such as nonuniform rational B-spline (NURBS) surfaces.
In a CAGD program, each object springs into existence at the time when it is created, either by execution of a user command, or as a result of reading data from a file. In most circumstances the new object is positioned, oriented or constructed in some deliberate relationship to one or more objects already in existence. For example, line B may be created in such a way that one of its endpoints is one end of a previously existing line A. However, the relationship which was clearly in the mind of the user at the time line B was created is not retained by the CAGD program; so if in some later revision of the geometry line A is displaced, then line B will stay where it is and no longer join line A. A conventional CAGD representation of geometry therefore consists of a large number of essentially independent simple objects, whose relationships are incidental to the manner and order in which they were created, but are not known to the program.
If design always proceeded in a forward direction, the loss of relationship information would not be a problem. One would start a project, add objects until the design is complete, and save the results. However, it is well known that engineering design is only rarely a simple forward process. It is far more commonly an iterative process: design is carried forward to some stage, then analyzed and evaluated; problems are identified; then the designer has to back up to some earlier stage and work forward again. It is typical that many iterative cycles are required, depending on the skills of the designer, the difficulty of the design specifications, and any optimization objectives that may be present. In each forward stage, the designer will have to repeat many operations he previously performed (updating), in order to restore relationships that were disrupted by the revision of other design elements. For example, he may have to move the end of line B so it once more joins line A; he may have to do this many times in the course of the design. CAGD systems typically provide extensive editing functions to facilitate these updates.
Revision of a previously existing design to meet new requirements is a common situation where similar problems are encountered. A change that alters an early stage of the design process requires at least one forward pass through all the subsequent design stages to restore disrupted relationships. Particularly if the relationships, and the sequence of design stages to achieve them, have been lost (and they are not normally retained in a way accessible to the user), the updating process can be very difficult, error-prone and time-consuming.
Some partial solutions to this problem are known. In some CAGD programs including AutoCAD, lines A and B can be created together as part of a "polyline" entity; then their connectivity will be automatically maintained if any of their endpoints, including their common point, are moved. Christensen (U.S. Pat. No. 4,663,616) has disclosed the concept of a "sticky" attribute which causes selected lines to remain connected to objects they are deliberately attached to. Draney (U.S. Pat. No. 4,829,446) has disclosed the concept of giving points in two dimensions serial numbers, and locating another point in two dimensions (a "Relative Point") by its relationship (x,y coordinate offsets) to a numbered point. Oosterholt (U.S. Pat. No. 4,868,766) has disclosed the concept of giving all geometric objects names, and locating each object in relationship to at most one other object, in a tree structure of dependency. Ota et al. (U.S. Pat. No. 5,003,498) have disclosed a CAGD system in which some objects have names, and are used by name in the construction of other more complex objects. Saxton (U.S. Pat. No. 4,912,657) discloses a system of "modular parametric design" in which design elements can be stored and conveniently recreated with different leading dimensions.
As mentioned above, many CAGD surface modeling systems support only a single type of surface, e.g. the FAIRLINE (R) surface, which is created from explicit cubic splines lofted through a set of B-spline "Master Curves". Although this surface can be molded into a wide variety of shapes useful in its own domain of ship hull design, there are many shapes it cannot make; e.g. it cannot form either an exact circular cross section or a completely round nose, both common features of submarine hulls. CAGD programs suited to mechanical design, such as AutoCAD, frequently support several simple surface types such as ruled surfaces and surfaces of revolution, but do not support more complex free-form surfaces such as B-spline parametric surfaces. Although it is widely appreciated that there would be large advantages in supporting a broader set of curve and surface types within a single CAGD environment, this has heretofore been possible only in workstation and mainframe CAGD systems, presumably because of the complexity of the programming required.
One known partial solution to this problem is to support only a single surface type, which has sufficient degrees of flexibility to encompass a useful set of simpler surfaces as special cases. Nonuniform rational B-spline (NURBS) surfaces have been proposed to fill this role, since by special choice of knots and coefficients the NURBS curve can accurately represent arcs of circles, ellipses, and other useful conic section curves. Disadvantages of this approach include the obscure relationship between the selection of knots and coefficients to achieve a desired curve; the large quantity of data required to define even a simple surface such as a circular cylinder; nonuniformity of resulting parameterizations; and the general unsuitability of NURBS surfaces for interactive design of surfaces having special requirements such as fairness or developability.
In CAGD surface modeling systems, intersections between surfaces often account for much of the complexity in both the program and the user interface. In a typical application, surface Y is constructed, then surface Z is constructed in such a way that it intersects surface Y. The next step is often to find the curve of intersection of Y and Z; then portions of Y and/or Z which extend beyond that curve may be discarded (trimmed). The problem of intersection of two surfaces is inherently difficult, for several reasons. The two surfaces may not intersect at all. Finding any single point of intersection requires solution of three simultaneous, usually nonlinear, equations. These equations will be ill-conditioned if the intersection is at a low angle. The intersection may be a single point, a simple arc, a closed curve, a self-intersecting curve, or multiple combinations of these elements. The surfaces might actually coincide over some finite area. Once a curve of intersection is found, it is often difficult to indicate correctly which portion of which surface is to be discarded. After trimming, a parametric surface patch may no longer be topologically quadrilateral, so it can no longer be conveniently parameterized.